package Z.dailyExercise.April;

import java.util.Arrays;
import java.util.HashSet;

public class _287寻找重复数 {
    /**
     * 思路1-直接排序
     * @param nums
     * @return
     */
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        int pivot = nums[0];
        int now = 1;
        while (nums[now] != pivot && now<nums.length){
            pivot = nums[now];
            now++;
        }

        return pivot;


    }
    /**
     * 借助hashset
     */
    public int findDuplicate1(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num:nums){
            if (set.contains(num)){
                return num;
            }else {
                set.add(num);
            }

        }
        return -1;

    }
    /**
     * 题解【1】：转化为链表求环的问题
     * 数组加上索引 看作一个环
     * 没看懂
     */
    /**
     * 题解【2】：原地hash
     * 直接将对应下表设为负数
     */
    public int findDuplicate2(int[] nums) {
        for (int i=0;i<nums.length;i++){
            if (nums[i] == i+1){
                continue;
            }
            int temp = nums[nums[i]-1];
            if (temp == nums[i]){
                return temp;
            }else {
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;
                i--;
            }

        }
        return -1;
    }

}
